package bintree.heap;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 基于泛型的最小堆实现
 * 元素从0开始编号
 * parent(i) = (i - 1) / 2;
 * left(i) = 2i + 1;
 * right(i) = 2i + 2;
 * @author yuisama
 * @date 2021/12/13 15:08
 **/
public class MinHeap<E extends Comparable<E>> {
    // 存储元素
    private List<E> elementData;

    public MinHeap() {
        elementData = new ArrayList<>();
    }

    public MinHeap(int capacity) {
        elementData = new ArrayList<>(capacity);
    }

    // heapify
    public MinHeap(E[] arr) {
        elementData = new ArrayList<>(arr.length);
        Collections.addAll(elementData,arr);
        // 从最后一个非叶子结点开始下沉，保证从子堆开始向上都是满足最小堆的性质
        for (int i = parent(getSize() - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    // 添加元素
    public void add(E val) {
        elementData.add(val);
        siftUp(getSize() - 1);
    }

    public E extractMin() {
        if (isEmpty()) {
            System.err.println("heap is empty!");
            return null;
        }else {
            E min = elementData.get(0);
            elementData.set(0,elementData.get(getSize() - 1));
            elementData.remove(getSize() - 1);
            siftDown(0);
            return min;
        }
    }

    /**
     * 元素下沉操作
     * @param i 要调整的元素索引
     */
    private void siftDown(int i) {
        // 只要还存在左子树
        while (leftChild(i) < getSize()) {
            int j = leftChild(i);
            if (j  + 1 < getSize() && elementData.get(j).compareTo(elementData.get(j + 1)) > 0) {
                j ++;
            }
            // j保存了左右孩子的最小值
            if (elementData.get(i).compareTo(elementData.get(j)) > 0) {
                swap(i,j);
                i = j;
            }else {
                // 此时i小于孩子
                break;
            }
        }
    }

    public E getMin() {
        if (isEmpty()) {
            System.err.println("heap is empty");
            return null;
        }
        return elementData.get(0);
    }

    /**
     * 元素上浮操作
     * @param i 要上浮的元素索引
     */
    private void siftUp(int i) {
        while (i > 0 && elementData.get(i).compareTo(elementData.get(parent(i))) < 0) {
            int j = parent(i);
            swap(i,j);
            i = j;
        }
    }

    /**
     * 交换数组中i和j的元素
     * @param i
     * @param j
     */
    private void swap(int i, int j) {
        E tmpVal = elementData.get(i);
        elementData.set(i,elementData.get(j));
        elementData.set(j,tmpVal);
    }

    // 求父节点索引
    private int parent(int i) {
        return (i - 1) / 2;
    }

    private int leftChild(int i) {
        return 2 * i + 1;
    }

    private int rightChild(int i) {
        return 2 * i + 2;
    }


    public boolean isEmpty() {
        return getSize() == 0;
    }

    public int getSize() {
        return elementData.size();
    }
}